\subsection{Necessary condition: Theorem~\ref{thm:necessary.symmetric}}
\label{sec:sym_necessary}

We show that the sufficient condition derived in
Theorem~\ref{thm:sufficient.symmetric} is also necessary upto
constants.

Let $k \in [n^{\frac{1}{10}},n^{\frac{9}{10}}]$ and $\alpha_i \in [n^{-1/100},n^{1/100}]$,
$i=1,2,\ldots,r$. Suppose we are given a bipartite graph $G=(V,W,E)$ which is the union
of complete bipartite graphs $G_1,G_2,\ldots,G_r$ and has no bipartite
independent set of size $k \times k$, where $G_i = (V_i,W_i,E_i=V_i
\times W_i)$ with $|V_i| = |W_i| = n_i = \alpha_i (n/k)$. We want to
show that for some constant $B > 0$,
\[ \sum_{i: \alpha_i \leq 1} \alpha_i^2 + \sum_{i: \alpha_i > 1} \alpha_i \geq B k \log n.\]

\noindent We will present the argument for the case when $k=\sqrt{n}$;
the proof for other $k$ is similar, and focussing on this $k$ will
keep the notation and the constants simple. We will show that if the
second term in the LHS of the above inequality is small, say,
\[ \secondterm = \sum_{i: \alpha_i > 1} \alpha_i \leq \frac{1}{100} k \log n,
\]
then the first term must be large, i.e.,
\[ \firstterm = \sum_{i: \alpha_i \leq 1} \alpha_i^2 \geq \frac{1}{100} k \log n.\]

Assume $\secondterm \leq \frac{1}{100} k \log n$. Let us call a $G_i$
for which $\alpha_i > 1$ as {\em large} and a $G_i$ for which
$\alpha_i \leq 1$ as {\em small}. We start as in \cite{RT} by deleting
one of the sides of each large $G_i$ independently and uniformly at
random from the vertex set of $G$.  For a vertex $v \in V$, let $d_v$
be number of large $G_i$'s such that $v \in V_i$. The probability that
$v$ survives at the end of the random deletion is precisely
$2^{-d_v}$. Now,
\[ \sum_{v} d_v = \sum_{i: \alpha_i > 1} n_i  \leq \frac{1}{100} n \log n,\]
where the inequality follows from our assumption that $\secondterm
\leq \frac{1}{100} k \log n$. That is, the average value of $d_v$ is
$\frac{1}{100} \log n$, and by Markov's inequality, at least half of
the vertices have their $d_v$'s at most $d=\frac{1}{50} \log n$. We
focus on a set $V'$ of $n/2$ such vertices, and if they survive the
first deletion, we delete them again with probability
$1-2^{-(d-d_v)}$, so that every one of these $n/2$ vertices in $V'$
survives with probability exactly $2^{-d}= n^{-1/50}$.  Let $X$ be the
vertices of $V'$ that survive. Similarly, we define $W' \subseteq W$,
and let $Y \subseteq W'$ be the vertices that survive.

\begin{claim}
With probability $1-o(1)$, $|X|, |Y| \geq \frac{n}{4}2^{-d}$.
\end{claim}

The claim can be proved as follows. For $v \in V'$, let $I_v$ be the
indicator variable for the event that $v$ survives. Then, $\Pr[I_v=1]=
2^{-d} = n^{-1/50}$ for all $v \in V'$.  Furthermore, $I_v$ and $I_{v'}$ are
dependent precisely if there is a common large $G_i$ such that both
$v, v' \in V_i$. Thus, any one $I_v$ is dependent on at most $\Delta =
d_v \times \max\{n_i: \alpha_i > 1\} \leq (1/50) \log n n^{1/100}
(n/k) = (1/50) n^{51/100} \log n$ such events (recall $k =
\sqrt{n}$). We thus have (see Alon-Spencer~\cite{AS})
\begin{eqnarray*}
 \E[|X|] & = & \sum_{v \in V'} I_v =\frac{n}{2}2^{-d} = \frac{1}{2}n^{49/50}; \\ 
 \var[|X|] &\leq & E[|X|] \Delta.
\end{eqnarray*}
By Chebyshev's inequality, the probability that $|X|$ is 
less than $\frac{\E[|X|]}{2}$ is at most 
\[ \frac{4\var[X]}{\E[|X|]^2} \leq \frac{4 \Delta}{\E[|X|]} = o(1). \]
A similar calculation can be done for $|Y|$.  (End of Claim.)

The crucial consequence of our random deletion process is that no
large $G_i$ has any edge between $X$ and $Y$.  Since $G$ does not have
any independent set $(S,T)$ of size $k \times k$, the small $G_i$'s
must provide the necessary edges to avoid such independent sets
between $X$ and $Y$. Consider an edge $(v,w)$ of a small $G_i$. The
probability that this edge survives in $X \times Y$ is precisely the
probability of the event $I_v \wedge I_w$. Note that the two events
$I_v$ and $I_w$ are either independent (when $v$ and $w$ do not belong
to a common large $G_i$), or they are mutually exclusive. Thus, the
expected number of edges supplied between $X$ and $Y$ by small $G_i$'s
is at most
\[ \sum_{i: \alpha_i \leq 1} \alpha_i^2 (n/k)^2 2^{-2d} = \firstterm \times (n/k)^2 2^{-2d}, \]
and by Markov's inequality, with probability $1/2$ it is at most twice
its expectation. Using the Claim above we conclude that the following
three events happen simultaneously: (a) $|X| \geq \frac{n}{4} 2^{-d}$,
(b) $|Y| \geq \frac{n}{4} 2^{-d}$, (c) the number of edges conecting
$X$ and $Y$ is at most $\firstterm \times (n/k)^2 2^{-2d}$. Using
(\ref{eq:kst-edges}), this number of edges must be at least
$\frac{1}{3} \frac{49}{50} \frac{(n2^{-d})^2}{16k} \log n$.  (Note
that $\frac{1}{3}$ suffices as the constant in (\ref{eq:kst-edges})
for the case $|X|, |Y| \geq \frac{n^{49/50}}{4}$ and $k = \sqrt{n}$.)
Comparing the upper and lower bounds on the number of edges thus
established, we obtain the required inequality
\[ \firstterm \geq \frac{1}{100} k \log n. \]
